class Solution {
public:
    vector<string> letterCombinations(string digits)
    {
        if (digits.empty()) return {};
        int n = digits.size();
        map<int, string> hash = { {2,"abc"},{3,"def"},{4,"ghi"},{5,"jkl"},{6,"mno"},{7,"pqrs"},{8,"tuv"},{9,"wxyz"} };
        vector<string> ans;
        string path(n, 0);
        function<void(int)> dfs = [&](int i) {
            if (i == n)
            {
                ans.push_back(path);
                return;
            }
            int x = digits[i] - '0';
            for (auto e : hash[x])
            {
                path[i] = e;
                dfs(i + 1);
            }
            };
        dfs(0);
        return ans;
    }
};